package main

import "fmt"

func main() {
	n := 10
	k := 7
	fmt.Print(combine(n, k))
}

func combine(n int, k int) [][]int {
	res := [][]int{}

	if k == 1 {
		for i := 1; i < n+1; i++ {
			temList := []int{i}
			res = append(res, temList)
		}
	} else {
		dfs([]int{}, k, n+1, 1, &res)
	}
	return res
}

func dfs(path []int, num int, total int, count int, res *[][]int) {
	if num == 2 {
		for i := count; i < total; i++ {
			for j := i + 1; j < total; j++ {
				fmt.Println(&path[0])
				temList := []int{i, j}
				fmt.Println(&temList[0])

				temList = append(temList, path...)
				//temList = append(path, temList...)
				fmt.Println(&temList[0])
				*res = append(*res, temList)
			}
		}
		return
	}

	for i := count; i < total+1-num; i++ {
		path = append(path, i)
		dfs(path, num-1, total, i+1, res)
		path = path[:len(path)-1]
	}
}

func combine1(n int, k int) (ans [][]int) {
	// 初始化
	// 将 temp 中 [0, k - 1] 每个位置 i 设置为 i + 1，即 [0, k - 1] 存 [1, k]
	// 末尾加一位 n + 1 作为哨兵
	temp := []int{}
	for i := 1; i <= k; i++ {
		temp = append(temp, i)
	}
	temp = append(temp, n+1)

	for j := 0; j < k; {
		comb := make([]int, k)
		copy(comb, temp[:k])
		ans = append(ans, comb)
		// 寻找第一个 temp[j] + 1 != temp[j + 1] 的位置 t
		// 我们需要把 [0, t - 1] 区间内的每个位置重置成 [1, t]
		for j = 0; j < k && temp[j]+1 == temp[j+1]; j++ {
			temp[j] = j + 1
		}
		// j 是第一个 temp[j] + 1 != temp[j + 1] 的位置
		temp[j]++
	}
	return
}

func combine2(n int, k int) (ans [][]int) {
	temp := []int{}
	var dfs func(int)
	dfs = func(cur int) {
		// 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
		if len(temp)+(n-cur+1) < k {
			return
		}
		// 记录合法的答案
		if len(temp) == k {
			comb := make([]int, k)
			copy(comb, temp)
			ans = append(ans, comb)
			return
		}
		// 考虑选择当前位置
		temp = append(temp, cur)
		dfs(cur + 1)
		temp = temp[:len(temp)-1]
		// 考虑不选择当前位置
		dfs(cur + 1)
	}
	dfs(1)
	return
}

func combine3(n int, k int) (ans [][]int) {
	if k == 1 {
		for i := 1; i < n+1; i++ {
			temList := make([]int, 1)
			temList[0] = i
			ans = append(ans, temList)
		}
	} else {
		path := []int{}
		var dfs func(int)
		dfs = func(count int) {
			if k-len(path) == 2 {
				for i := count; i < n+1; i++ {
					for j := i + 1; j < n+1; j++ {
						temList := make([]int, 2)
						temList[0], temList[1] = i, j
						temList = append(path, temList...)
						ans = append(ans, temList)
					}
				}
				return
			}

			for i := count; i < n+2-k-len(path); i++ {
				path = append(path, i)
				dfs(i + 1)
				path = path[:len(path)-1]
			}
		}
		dfs(1)
	}
	return

}
